package lc;

import org.junit.Test;

import util.BracketUtils;

public class Ex378 {
    class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            //双重二分
            int m = matrix.length, n = matrix[0].length, lo = matrix[0][0], hi = matrix[m - 1][n - 1];
            while (lo < hi) {
                int mid = (hi + lo) / 2;
                int cnt = count(matrix, mid);
                System.out.println(lo + "\t" + mid + "\t" + hi + "\t" + cnt + "\t");
                if (cnt < k) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            return lo;
        }
    
        public int count(int[][] nums, int max) {
            int m = nums.length, n = nums[0].length, cnt = 0;
            for (int i = 0; i < m; i++) {
                int lo = 0, hi = n - 1;
                while (lo < hi) {
                    int mid = (hi + lo) / 2;
                    if (nums[i][mid] <= max) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                if (nums[i][lo] > max) {
                    cnt += lo;
                } else {
                    cnt += n;
                }
            }
            return cnt;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[-5,-4],[-5,-4]]");
        System.out.println(s.kthSmallest(nums, 8));
    }
}
